/*
 * @lc app=leetcode.cn id=432 lang=cpp
 *
 * [432] 全 O(1) 的数据结构
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <unordered_map>
#include <cmath>

using namespace std;
// @lc code=start
class AllOne {
    //双向链表+哈希表
public:
    unordered_map<string,int> mp;
    //升序队列，小顶堆
    priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>> p;
    priority_queue<pair<int,string>,vector<pair<int,string>>,less<pair<int,string>>> q;

    AllOne() {
        
    }
    
    void inc(string key) {
        mp[key]++;
        p.push(make_pair(mp[key],key));
        q.push(make_pair(mp[key],key));//每次更新的时候，都会在大根堆小根堆中push（所以会有很多冗杂的信息，后续再删除）
    }
    
    void dec(string key) {
        mp[key]--;
        if(mp[key]==0)
        {
            mp.erase(key);//删除这个键
            return;
        }
        p.push(make_pair(mp[key],key));
        q.push(make_pair(mp[key],key));//每次更新的时候，都会在大根堆小根堆中push
    }
    
    string getMaxKey() {
        if(mp.size()==0){
            return "";
        }
        while(mp[q.top().second] != q.top().first){
            q.pop();//之前我们在堆中Push的元素，有不少是完全没有意义，只是垫位置用的，所以我们在获取答案的时候，要将哈希表中对应值不一样的pair给移除。（因为对应值不一样的，是在更新键值未完成之前push的，说白了，就是垫位置）。
        }
        return q.top().second;
    }
    
    string getMinKey() {
        if(mp.size()==0) {
            return "";
        }
        while(mp[p.top().second] != p.top().first) {
            p.pop();
        }
        return p.top().second;
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */
// @lc code=end

